package arithmetic2.day04;

import java.util.Arrays;
import java.util.Iterator;
import java.util.List;
import java.util.Stack;

/*
    判断一个链表是否回文
 */
public class Demo03 {
    public static void main(String[] args) {
        List<Integer> list = Arrays.asList(1, 2, 2, 1);
        System.out.println(isHuiWen(list));
    }

    //使用栈，空间复杂度为N
    public static boolean isHuiWen(List<Integer> list) {
        Stack<Integer> stack = new Stack<>();
        for (Integer num : list) {
            stack.push(num);
        }
        int index = 0;
        while (!stack.empty()) {
            Integer num = stack.pop();
            if (num != list.get(index)) {
                return false;
            }
            index++;
        }
        return true;
    }

    //不使用额外变量，空间复杂度为1
    public static boolean isHuiWen2(List<Integer> list) {
        //遍历链表，将头节点和尾节点和中间节点保存
        Integer head = null;
        Integer mid = null;
        Integer tail = null;
        Iterator<Integer> iterator = list.iterator();
        int index = 0;
        while (iterator.hasNext()) {
            if (index == 0) {
                head = iterator.next();
            }
            if (index == (list.size()-1) >> 1) {
                mid = iterator.next();
            }
            if (index == list.size() - 1) {
                tail = iterator.next();
            }
        }
        return false;
    }
}
